import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 面试题 03.06. 动物收容所
 * https://leetcode-cn.com/problems/animal-shelter-lcci/
 */
public class Solutions_mianshi_03_06 {
    public static void main(String[] args) {
//        AnimalShelf obj = new AnimalShelf();
//        obj.enqueue(new int[]{0, 0});
//        obj.enqueue(new int[]{1, 0});
//        int[] res1 = obj.dequeueCat();  // output: {0, 0}
//        System.out.println(Arrays.toString(res1));
//        int[] res2 = obj.dequeueDog();  // output: {-1, -1}
//        System.out.println(Arrays.toString(res2));
//        int[] res3 = obj.dequeueAny();  // output: {1, 0}
//        System.out.println(Arrays.toString(res3));

        AnimalShelf obj = new AnimalShelf();
        obj.enqueue(new int[]{0, 0});
        obj.enqueue(new int[]{1, 0});
        obj.enqueue(new int[]{2, 1});
        int[] res1 = obj.dequeueDog();  // output: {2, 1}
        System.out.println(Arrays.toString(res1));
        int[] res2 = obj.dequeueCat();  // output: {0, 0}
        System.out.println(Arrays.toString(res2));
        int[] res3 = obj.dequeueAny();  // output: {1, 0}
        System.out.println(Arrays.toString(res3));
    }
}

/**
 * 解法二：两个队列实现
 */
class AnimalShelf {
    private Queue<int[]> queueCat;
    private Queue<int[]> queueDog;

    public AnimalShelf() {
        queueCat = new LinkedList<>();
        queueDog = new LinkedList<>();
    }

    public void enqueue(int[] animal) {
        if (animal[1] == 1) {
            // 添加到“动物狗”队列
            queueDog.offer(animal);
        } else {
            // 添加到“动物猫”队列
            queueCat.offer(animal);
        }
    }

    public int[] dequeueAny() {
        if (queueDog.isEmpty() && queueCat.isEmpty()) {
            // 两个队列都为空时
            return new int[]{-1, -1};
        }
        if (queueCat.isEmpty() || queueDog.isEmpty()) {
            // 其中一个队列为空时
            return queueDog.isEmpty() ? queueCat.poll() : queueDog.poll();
        }
        // 比较，编号最小的就是“收容”时间最长的
        int[] dog = queueDog.peek();
        int[] cat = queueCat.peek();
        return dog[0] < cat[0] ? queueDog.poll() : queueCat.poll();
    }

    public int[] dequeueDog() {
        if (queueDog.isEmpty()) {
            return new int[]{-1, -1};
        }
        return queueDog.poll();
    }

    public int[] dequeueCat() {
        if (queueCat.isEmpty()) {
            return new int[]{-1, -1};
        }
        return queueCat.poll();
    }
}

/**
 * 解法一：一个队列实现
 */
class AnimalShelf1 {
    private Queue<int[]> queue;

    public AnimalShelf1() {
        queue = new LinkedList<>();
    }

    public void enqueue(int[] animal) {
        queue.add(animal);
    }

    public int[] dequeueAny() {
        if (queue.isEmpty()) {
            return new int[]{-1, -1};
        }
        return queue.poll();
    }

    public int[] dequeueDog() {
        // 遍历队列，找到第一个入队的动物“狗”
        for (int[] ele : queue) {
            // 动物类别：狗 = 1
            if (ele[1] == 1) {
                queue.remove(ele);
                return ele;
            }
        }
        return new int[]{-1, -1};
    }

    public int[] dequeueCat() {
        // 遍历队列，找到第一个入队的动物“猫”
        for (int[] ele : queue) {
            // 动物类别：猫 = 0
            if (ele[1] == 0) {
                queue.remove(ele);
                return ele;
            }
        }
        return new int[]{-1, -1};
    }
}
